package com.faxon.leetcode.d;

import org.junit.Test;

/**
 * @author Faxon
 * @version 1.0
 * @date 2020-04-14 12:34
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 你可以假设数组中无重复元素。
 * 示例 1:
 * 输入: [1,3,5,6], 5
 * 输出: 2
 * <p>
 * 示例 2:
 * 输入: [1,3,5,6], 2
 * 输出: 1
 * <p>
 * 示例 3:
 * 输入: [1,3,5,6], 7
 * 输出: 4
 * <p>
 * 示例 4:
 * 输入: [1,3,5,6], 4
 * 输出: 0
 **/
public class LeetCode35 {
    /**
     * 二分查找
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            }
        }
        //low与high相等
        return nums[low] >= target ? low : (low + 1);
    }


    @Test
    public void tsetSearchInsert() {
        int[] nums = new int[]{1, 3, 5, 7, 10, 20, 21, 22};
        int i = searchInsert(nums, 6);
        System.out.println(i);
    }

}
